// bzoj2662
// 题意：给定一个边上费用为偶数的无向联通图，可以选择路径上最多k条边使得时间
//       费用减半，问从1到n最少费用。
//
// 题解：由于n比较小，就构建一个k层的分层图跑最短路就好。
//       dijkstra模板。
//
// run: $exec < input
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <functional>

struct node { int to, cost; };

int const inf = 1 << 29;
int const maxn = 3000;

std::vector<node> graph[maxn];
typedef std::vector<node>::iterator edge_iter;

int n, m, k, s, t;

int index_kth(int x, int k)
{
	return x + k * n;
}

void add_edge(int x, int y, int z)
{
	graph[x].push_back({y, z});
}

int dijkstra(int source, int target)
{
	int num = t + 4; // tot vertices FIXME
	int dist[num];
	std::fill(dist, dist + num, inf);
	dist[source] = 0;
	typedef std::pair<int, int> cost_end;
	std::priority_queue<cost_end, std::vector<cost_end>, std::greater<cost_end> > pq;
	pq.push(std::make_pair(0, source));
	while (!pq.empty()) {
		cost_end tmp = pq.top(); pq.pop();
		int u = tmp.second;
		if (dist[u] < tmp.first) continue;

		for (edge_iter edge = graph[u].begin(); edge != graph[u].end(); ++edge) {
			int v = edge->to, c = edge->cost;
			if (dist[v] > dist[u] + c) {
				dist[v] = dist[u] + c;
				pq.push(std::make_pair(dist[v], v));
			}
		}
	}
	return dist[target];
}

int main()
{
	std::cin >> n >> m >> k;
	s = index_kth(0, k);
	t = index_kth(n-1, k) + 1;
	for (int i = 0, x, y, z; i < m; i++) {
		std::cin >> x >> y >> z;
		x--; y--;
		for (int j = 0; j <= k; j++) {
			int u = index_kth(x, j);
			int v = index_kth(y, j);
			add_edge(u, v, z);
			add_edge(v, u, z);
			if (j == 0) continue;
			add_edge(u, index_kth(y, j-1), z/2);
			add_edge(v, index_kth(x, j-1), z/2);
		}
	}
	for (int i = 0; i <= k; i++)
		add_edge(index_kth(n-1, i), t, 0);
	int ans = dijkstra(s, t);
	std::cout << ans << '\n';
}

